package reviewAlgorithms.search;

public class Exist {
    private  static int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};

    public static void main(String[] args) {
        String word = "ABCESEEEFS";
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','E','S'},
                {'A','D','E','E'}
        };
        System.out.println(exist(board,word));
    }
    public static boolean exist(char[][] board, String word) {
        if (board == null || board.length < 1){
            return false;
        }
        if (word == null || word.length() < 1) {
            return true;
        }
        int start = 0;
        int rowNum = board.length;
        int columnNum = board[0].length;
        int maxNum = rowNum*columnNum;
        for (int i = 0; i < maxNum; i++) {
            int row = i / columnNum;
            int column = i % columnNum;
            if (board[row][column] == word.charAt(0)){
                int[][] state = new int[board.length][board[0].length];
                if (getExist(board,word,row,column,start,state)){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean getExist(char[][] board, String word, int row, int column, int start, int[][] state) {
        if (start  >= word.length()){
            return true;
        }
        if (row < 0 || column < 0 || row >= board.length || column >= board[0].length){
            return false;
        }
        if (state[row][column] == 0 && board[row][column] == word.charAt(start)) {
            System.out.println(word.charAt(start));
            state[row][column] = 1;
            for (int[] aDirection : direction) {
                int newRow = aDirection[0] + row;
                int newColumn = aDirection[1] + column;
                if (getExist(board, word, newRow, newColumn, start + 1, state)){
                    return true;
                }
            }
            state[row][column] = 0;
        }
        return false;
    }
}
